package leetcode_jz_offer;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 美女
 * @date 2022/08/29 16:36
 **/

/**
 * 队列尾部插入元素时，我们可以提前取出队列中所有比这个元素小的元素，使得队列中只保留对结果有影响的数字。
 * 这样的方法等价于要求维持队列单调递减，即要保证每个元素的前面都没有比它小的元素。
 * 注意取元素时只能从队尾取，因为队首元素可能大于当前元素。应用到双端队列
 */
public class Num59_II_队列的最大值 {
    Queue<Integer> q;
    Deque<Integer> d;//辅助队列，存放队列结果的最大值【最大值从队尾插入从队首出队，中途取出比最大值小的值时从队尾出队取出小值】
    public Num59_II_队列的最大值() {
        q=new LinkedList<>();
        d=new LinkedList<>();
    }

    public int max_value() {//队列为空时返回-1
        if (d.isEmpty()){
            return -1;
        }
        return d.peekFirst();
    }

    public void push_back(int value) {
        q.offer(value);//入队
        //将入队元素与双端队列中元素对比，将比value小的元素从双端队列出队，将val入队
        while (!d.isEmpty()&&d.peekLast()<value){
            d.pollLast();
        }
        d.addLast(value);
    }

    public int pop_front() {//队列为空时返回-1
        if(q.isEmpty()){
            return -1;
        }
        int temp=q.poll();
        //当双端队列的值和队列出队元素相等时双端队列队首元素也需要出队
        if(temp==d.peekFirst()){
            d.pollFirst();
        }
        return temp;
    }
}
